//给定一个长度为 n 的链表 head 
//
// 对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。 
//
// 返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点
//，设置 answer[i] = 0 。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：head = [2,1,5]
//输出：[5,5,0]
// 
//
// 示例 2： 
//
// 
//
// 
//输入：head = [2,7,4,3,5]
//输出：[7,0,5,5,0]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点数为 n 
// 1 <= n <= 10⁴ 
// 1 <= Node.val <= 10⁹ 
// 
//
// Related Topics 栈 数组 链表 单调栈 👍 285 👎 0


package leetcode.editor.cn;

// [1019]链表中的下一个更大节点

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

public class NextGreaterNodeInLinkedList_1019 {
    public ListNode makeList(int[] arr){
        if (arr.length==0){
            return null;
        }else {
            ListNode head = new ListNode(arr[0]);
            ListNode cur = head;
            for (int i = 1; i < arr.length; i++) {
                cur.next = new ListNode(arr[i]);
                cur = cur.next;
            }
            return head;
        }
    }

    public static void main(String[] args) {
        Solution solution = new NextGreaterNodeInLinkedList_1019().new Solution();
        int[] test = new int[]{2,1,5};
        ListNode head = new NextGreaterNodeInLinkedList_1019().makeList(test);
//        System.out.println(head.toString());
        System.out.println(Arrays.toString(solution.nextLargerNodes(head)));
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public int[] nextLargerNodes(ListNode head) {
            Stack<int[]> stack = new Stack<>();
            ArrayList<Integer> list = new ArrayList<>();
            ListNode cur = head;
            int idx = 0;
            while (cur != null) {
                list.add(0);
                while (!stack.isEmpty() && cur.val > stack.peek()[0]) {
                    list.set(stack.pop()[1], cur.val);
                }
                stack.push(new int[]{cur.val, idx++});
                cur = cur.next;
            }
            int[] ans = new int[list.size()];
            for (int i = 0; i < ans.length; i++) {
                ans[i] = list.get(i);
            }
            return ans;
        }
    }

    //leetcode submit region end(Prohibit modification and deletion)
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }
}